package pers.vic.basics.leetcode;

import sun.awt.SunGraphicsCallback;

import javax.annotation.Resource;
import java.awt.*;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Stack;

/**
 * @author Vic.xu
 * @description:25. K 个一组翻转链表 {@literal https://leetcode-cn.com/problems/reverse-nodes-in-k-group/}
 * @date: 2020/11/17 0017 8:57
 */
public class J0025_H_ReverseKGroup {
    /*
    给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
    k 是一个正整数，它的值小于或等于链表的长度。
    如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
     */
    /*
    你的算法只能使用常数的额外空间。
    你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
     */

    /**
     * 这是我首先通过栈的方式写的
     */
    public static ListNode reverseKGroup2(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        //入栈的数量
        int len = 0;
        while (cur != null && len < k) {
            stack.push(cur);
            cur = cur.next;
            len++;
        }
        //长度不够 原路返回
        if (len < k) {
            return head;
        }
        //反转链表
        ListNode dummy = new ListNode();
        ListNode pop = dummy;
        while (!stack.empty()) {
            ListNode node = stack.pop();
            pop.next = node;
            if (node != null) {
                //断掉后面的链
                node.next = null;
            }
            pop = pop.next;
        }
        //如果剩下的链表不为空，递归翻转
        if (cur != null) {
            pop.next = reverseKGroup(cur, k);
        }
        return dummy.next;
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null){
            return head;
        }
        int n = 1;
        ListNode p = head;
        while (p.next != null && n != k) {
            p = p.next;
            n++;
        }
        if (n < k) {
            return head;
        }
        //当前节点的 后的节点的反转
        p.next = reverseKGroup(p.next, k);
        //反转head 到 当前节点
        head = reverse(head, p.next);
        return head;

    }

    /**
     * 反转区间链表[start, end) 前包含 后不包含:反转过程如下：
     * 1-2-3-4        5
     * 2-3-4        1-5
     * 3-4        2-1-5
     * 4        3-2-1-5
     * 4-3-2-1-5
     */
    public static ListNode reverse(ListNode start, ListNode end) {
        ListNode result = end;
        //前部分 中剩下的
        ListNode leave = start;
        ListNode temp = null;
        while (leave != end) {
            ListNode head = leave;
            //减去头部
            leave = leave.next;
            //把头部放到end的头部
            head.next = result;
            result = head;
        }
        return result;
    }

    public static void main(String[] args) {
        //1->2->3->4->5
        /*
        ListNode head = new ListNode(new int[]{1, 2, 3, 4, 5});
        ListNode tail = head.next.next.next;
        ListNode node = reverse(head, tail);
        System.out.println(node);
        System.out.println("----------------------------------");
        ListNode.print(head);
        //当 k = 2 时，应当返回: 2->1->4->3->5
//        System.out.println(reverseKGroup(head, 2));

         */
//
        ListNode listNode = new ListNode(new int[]{1, 2, 3, 4, 5, 6, 7});
        //当 k = 3 时，应当返回: 3->2->1->4->5
        System.out.println(reverseKGroup(listNode, 3));
    }
}
